UNRELIABILITY LOWER-BOUND ESTIMATE OF NONBRANCHING PROGRAMMES
WITH A CONDITIONAL STOP OPERATOR

Alekhina Marina Anatolyevna, Doctor of physical and mathematical sciences, professor, head of sub-department of discrete mathematics, Penza State University, dm@pnzgu.ru
Grabovskaya Svetlana Mikhaylovna, Senior lecturer, sub-department of discrete mathematics, Penza State University, swetazin@mail.ru

519.718

The article considers a problem of synthesis of nobranching programs with conditional stop-operator. All functional operators are supposed to be subject to out-put inverse failures with probability  ε (ε∈(0,1/2). Conditional stop-operators are absolutely reliable. Any boolean function f∈K (class K is found explicitly) is proved to be impossible to realize by irreducible nobranching program with unreliability of less than ε(1 – ε)^m, where m – the number of functional operators in the program. These and the previous results on the upper bound for the unreliability of the nobranching programs prove that almost all functions can be realized by asymptotically optimal reliable nobranching programs that operate with unreliability asymptotically equal to ε at ε → 0.

boolean functions, nobranching programs, conditional stop-operator, synthesis, reliability